| 翻訳と辞書 |
| Stanley–Wilf conjecture ： ウィキペディア英語版 |
Stanley–Wilf conjecture
The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that every permutation pattern defines a set of permutations whose growth rate is singly exponential. It was proved by and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to , which had been shown to imply the Stanley–Wilf conjecture by .
==Statement==
The Stanley–Wilf conjecture states that for every permutation ''β'', there is a constant ''C'' such that the number |''S''''n''(''β'')| of permutations of length ''n'' which avoid ''β'' as a permutation pattern is at most ''C''''n''. As observed, this is equivalent to the convergence of the limit
:
The upper bound given by Marcus and Tardos for ''C'' is exponential in the length of ''β''. A stronger conjecture of had stated that one could take ''C'' to be , where ''k'' denotes the length of ''β'', but this conjecture was disproved for the permutation by . Indeed, has shown that ''C'' is, in fact, exponential in ''k'' for almost all permutations.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Stanley–Wilf conjecture」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|